def split_public(public):
    """
    Split Public Key into Components
    """
    y = public[:16]
    g = public[16:32]
    p = public[32:]
    return y, g, p

def split_ciphertext(ciphertext):
    """
    Split Ciphertext into a and b
    """
    a = ciphertext[:16]
    b = ciphertext[16:]
    return a, b

def decrypt_message(a, b, x, p):
    a = int(a, 2)
    b = int(b, 2)
    x = int(x ,2)
    p = int(p, 2)
    message = (b * _mod_inverse(a**x % p, p)) % p
    return _dec_to_bin(message)[8:]

def _mod_inverse(b, m):
    """
    Extended Euclidean Algorithm (from William Stallings' "Cryptography and
    Network Security", Fourth Edition)
    """
    a1, a2, a3 = 1, 0, m
    b1, b2, b3 = 0, 1, b
    while True:
        if b3 == 0:
            return None
        if b3 == 1:
            return b2 % m
        q = a3/b3
        t1, t2, t3 = a1-q*b1, a2-q*b2, a3-q*b3
        a1, a2, a3 = b1, b2, b3
        b1, b2, b3 = t1, t2, t3

def _dec_to_bin(decimal):
    binary_reps = {'0': '000',
                   '1': '001',
                   '2': '010',
                   '3': '011',
                   '4': '100',
                   '5': '101',
                   '6': '110',
                   '7': '111'
    }
    oct_rep = str(oct(decimal))
    binary_string = ""
    for c in oct_rep:
        if c != "L":
            binary_string += binary_reps[c]
    if len(binary_string) > 16:
        binary_string = binary_string[len(binary_string) - 16:]
    while len(binary_string) < 16:
        binary_string = "0" + binary_string
    return binary_string